/**
*      author: Y_Yao
*      created: 2024-11-30 14:26:07
**/

#include<bits/stdc++.h>

using namespace std;
using LL = long long;
const LL LLINF = 1e18;
const int INF = 0x3f3f3f3f;
const int N = 3.2e4 + 7;
int dp[N],mw[N],mv[N],fw[N][3],fv[N][3];
int n,m;

void solve()
{
    cin >> n >> m;
    for(int i = 1;i <= m;i++)
    {
        int w,v,q;
        cin >> w >> v >> q;
        if(q == 0)
        {
            mw[i] = w;
            mv[i] = w * v;
        }
        else
        {
            fw[q][0]++;
            fw[q][fw[q][0]] = w;
            fv[q][fw[q][0]] = w * v;
        }
    }

    for(int i = 1;i <= m;i++)
    {
        for(int j = n;j >= mw[i];j--)
        {
            dp[j] = max(dp[j],dp[j - mw[i]] + mv[i]);
            if(j >= mw[i] + fw[i][1])
            {
                dp[j] = max(dp[j],dp[j - mw[i] - fw[i][1]] + mv[i] + fv[i][1]);
            }
            if(j >= mw[i] + fw[i][2])
            {
                dp[j] = max(dp[j],dp[j - mw[i] - fw[i][2]] + mv[i] + fv[i][2]);
            }
            if(j >= mw[i] + fw[i][1] + fw[i][2])
            {
                dp[j] = max(dp[j],dp[j - mw[i] - fw[i][2] - fw[i][1]] + mv[i] + fv[i][2] + fv[i][1]);
            }
        }
    }

    cout << dp[n] << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}